Problem statement: zenit12ckl

Jeden z udávateľov trendov farmárskej profesie na Slovensku Mic sa zberá na svoj farmársky dôchodok. Na svoje staré kolená bude radšej programátorom. Rozhodol sa, že svoju farmu predá.

Mic má úrodné pole s rozlohou veľa hektárov. Toto pole má obdĺžnikový tvar a je rozdelené na veľa štvorcov veľkosti jeden hektár. Mic zastáva názor, že chlieb, pivo a lenivosť sú najzákladnejšie veci v živote človeka. Z toho dôvodu na každej z týchto štvorcových oblastí pestuje jačmeň, pšenicu alebo nič.

Žiaľ, nenašiel sa nikto, kto by bol schopný prevziať celé hospodárstvo. Podarilo sa mu ale nájsť kupca, ktorý má záujem o časť poľa. Presnejšie, tento kupec chce kúpiť dve obdĺžnikové oblasti. Strany týchto obdĺžnikov majú byť rovnobežné s hranicami veľkého poľa a nesmú rozdeľovať malé štvorcové hektárové územia (každý štvorcový hektár je obsiahnutý celý alebo vôbec). Tieto dva obdĺžniky sa nesmú pretínať. Je ale povolené, aby sa ich hranice dotýkali. Keďže nevedno, aký bude ďalší burzový vývoj pšenice a jačmeňa, chce záujemca kúpiť pole tak, aby boli rozlohy území, kde sa pestuje pšenica a jačmeň približne rovnako veľké. Jeho požiadavkou je, aby sa počet jačmenných hektárov nelíšil od počtu pšeničných o viac ako K (hektárov, na ktorých sa aktuálne nepestuje nič, môže byť ľubovoľný počet). Dôležitý je rozdiel v oboch obdĺžnikoch spolu. V rámci jedného obdĺžnika neplatia žiadne odmedzenia.

Napíšte Micovi program, ktorý vypočíta, koľko najviac poľa je schopný predať. Na prvom riadku vstupu sú rozmery poľa R,S a číslo K. Platí 1 ≤ R,S ≤ 30 a 0 ≤ K ≤ R·S. Nasleduje popis, čo sa pestuje na ktorom hektári poľa. Na každom z ďalších R riadkov je S znakov. Každý z týchto znakov je 'J', 'P' alebo '.'. Bodka označuje, že na danom hektári sa aktuálne nepestuje nič.

Na jediný riadok výstupu vypíšte jedno číslo: koľko najviac hektárov poľa môžeme predať, ak má kupec záujem o dve neprázdne nepretínajúce sa obdĺžnikové oblasti a rozdiel počtu jačmenných a pšeničných hektárov nemá byť viac ako K.

Existuje viacero rôzne efektívnych riešení. Ak nestíhate alebo neviete vzorové, tak aj za pomalšie môže byť netriviálne veľa bodov (20 až 35 podľa jeho rozumnosti). Na testovači máte okrem týchto ešte jeden sample, ktorý je veľký.

3 3 1
JJJ
PPP
JJJ

    
  

7

    
  

6 7 2
JJPJ.JP
PJPPPPJ
J.P.PJJ
JPJJJP.
.JJJJP.
PPJJ.JJ

    
  

35

    
  

2 2 1
PP
PP

    
  

0